/*Copyright (C) 2013-2021 LZE*/
#include<bits/stdc++.h>
#define fo(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define INF 0x7fffffff
#define mod 1000000007
#define eps 1e-6
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 35;
const int M = 225;
ll n,V,T;
ll KP[15][N] = {0},w[N],c[N];
ll f[M];
int main() {
    ll p;
	scanf("%lld%lld%lld",&V,&n,&T);
    for(ll i = 1;i <= n;i++){
        scanf("%lld%lld%lld",&w[i],&c[i],&p);
        KP[p][++KP[p][0]] = i;
    }
    for(ll i = 1;i <= T;i++){
        for(ll k = V;k >= 0;k--){
            for(ll j = 1;j <= n;j++){
                ll x = KP[i][j];
                // cout << f[j][k] << endl;
                if(k - w[x] >= 0){
                    f[k] = max(f[k],f[k - w[x]] + c[x]);
                }
            }
        }
    }
    printf("%lld\n",f[V]);
	return 0;
}
